/*
 * 1181. Diameter of Binary Tree
 * Given a binary tree, you need to compute the length of the diameter of the tree. 
 * The diameter of a binary tree is the length of the longest path between any two nodes in a tree. 
 * This path may or may not pass through the root.
 * https://www.lintcode.com/problem/diameter-of-binary-tree/description
 * 
 * 样例
 * Given a binary tree 
 * 		1
 * 	   / \
 * 	  2   3
 *   / \     
 *  4   5    
 *  Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
 * 
 * 2018.06.16 @jeyming
 */
package diameter_of_binary_tree_1181;

//import java.util.Queue;
//import java.util.concurrent.ArrayBlockingQueue;

/**
 *Definition of TreeNode:
 */
class TreeNode {
	public int val;
	public TreeNode left, right;
	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}

public class diameter_of_binary_tree_1181 {
	/**
	 * @param root: a root of binary tree
	 * @return: return a integer
	 */
	//求二叉树的深度
	public int treeDepth(TreeNode p) {
		if(p == null) {
			return 0;
		}
		int nLeft = treeDepth(p.left);
		int nRight = treeDepth(p.right);
		return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
	}
	
	public int diameterOfBinaryTree(TreeNode root) {
		// write your code here
//		Queue<TreeNode> queue = new ArrayBlockingQueue<TreeNode>(1000);
//		queue.add(root);
//		int cnt = 0;
//		int cntTree = 0;
//		int sumTree = 2;
//		while(queue.peek() != null) {
//			if(queue.peek().left != null) {
//				queue.add(queue.peek().left);
//			}
//			if(queue.peek().right != null) {
//				queue.add(queue.peek().right);
//			}
//			cntTree += 2;
//			queue.remove();
//			if(cntTree == Math.pow(2, sumTree - 1)) {
//				if(cntTree >= 2) {
//					cnt += 2;
//				} else if(cntTree == 1) {
//					cnt += 1;
//				} 
//				sumTree += 1;
//				cntTree = 0;
//			}
//			
//		}
//		return cnt;
		if(root == null)
			return 0;
		if((root.left == null) || (root.right == null))
			return treeDepth(root.left) + treeDepth(root.right);
		else
			return treeDepth(root.left) + treeDepth(root.right) + 1;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
